/*
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <stdlib.h>
#include <memory.h>
#include "boost/thread/mutex.hpp"

#define FL_BLOCK_BASE (1<<16)

template <class T>
class FreeList
{
public:
	FreeList(const bool bDeconstruct=false) :
		iBlockSize(FL_BLOCK_BASE / sizeof(T)),
		bDeconstruct(bDeconstruct)
	{
		//using huge objects here is nonsense
		//assert(iBlockSize);
		
		//initialize members
		ppCurr=nullptr;
		ppFreeList=nullptr;
		ppListEnd=nullptr;
		ppBlocks=nullptr;
		nBlocks=0;
	}

	~FreeList()
	{
		//free blocks
		for(unsigned int i=0; i<nBlocks; i++)
		{
			if(bDeconstruct)
				for(unsigned int j=0; j<iBlockSize; j++)
					ppBlocks[i][j].~T();
					
			free(ppBlocks[i]);
		}
		//free block list itself
		if(ppBlocks != nullptr)
			free(ppBlocks);
			
		//free free list
		if(ppFreeList != nullptr)
			free(ppFreeList);
	}

	T*
	checkOut()
	{
		boost::unique_lock<boost::mutex> scoped_lock(mutex);
		if(ppCurr==ppListEnd)
		{
			//reserve another block
			T* pBlock=(T*) malloc((size_t)FL_BLOCK_BASE);
			if(!pBlock)
				return nullptr;
			//increase block count
			ppBlocks=(T**) realloc(ppBlocks, (nBlocks + 1)*sizeof(T*));
			if(!ppBlocks)
				return nullptr;
				
			ppBlocks[nBlocks]=pBlock;
			nBlocks++;
			//update free list
			ppFreeList =(T**)  realloc(ppFreeList, nBlocks*iBlockSize*sizeof(T*));
			if(!ppFreeList)
				return nullptr;

			ppListEnd = ppFreeList + nBlocks*iBlockSize;
			ppCurr = ppFreeList + (nBlocks - 1)*iBlockSize;

			const unsigned int iListOffset=(nBlocks - 1)*iBlockSize;
			for(unsigned int j=0; j < iBlockSize; j++)
			{
				ppFreeList[iListOffset + j]=pBlock + j;
			}
		}

		return *(ppCurr++);
	}

	void
	checkIn(T* p)
	{
		boost::unique_lock<boost::mutex> scoped_lock(mutex);
		*(--ppCurr)=p;
	}

	T*
	construct()
	{
		T* p=this->checkOut();
		*p=T();
		return p;
	}

	void
	deconstruct(T* p)
	{
		p->~T();
		checkIn(p);
	}
	
	void
	getStatus(unsigned int& reserved, unsigned int& used, unsigned int& free)
	{
		reserved=iBlockSize * nBlocks;
		used=(ppCurr-ppFreeList);
		free=reserved-used;
	}
	
	void
	consolidate()
	{
		//NIY
	}
	
	void
	reserve(unsigned int elems)
	{
		//NIY
	}
	
private:
	//core functionality
	T** ppCurr;
	T** ppFreeList;
	T** ppListEnd;

	//block management
	T** ppBlocks;
	unsigned int nBlocks;
	const unsigned int iBlockSize;
	
	//misc
	const bool bDeconstruct;

	boost::mutex mutex;
};
